public class GreedyAlgorithm {
    private int n = 0; //item数量
    private int[] item_weight; //每一个item的重量
    private int[] item_values; //每一个item的值
    private int m = 0; //背包数量
    private int[][] isAdd; //item是否被放入某个背包中，最后一位存放是否能被放入现有背包空余，1为否
    private int[] weight; //各背包目前可承重
    private int[] weighted; //背包已承重
    private int[] bag_value; //背包价值
    private float[] benefits; //item的value与weight的比值


    public GreedyAlgorithm() {
        n = (int) (Math.random() * 16 + 10);//默认初始化时，背包和物品的个数都是随机生成的
        m = (int) (Math.random() * 10 + 1);
        item_weight = new int[n];
        item_values = new int[n];
        weight = new int[m];
        weighted = new int[m];
        bag_value = new int[m];
        benefits = new float[n];
        isAdd = new int[n][m + 1];
        initiate();
        sort();
    }

    public GreedyAlgorithm(int n, int m, int[] item_weight, int[] item_values, int[][] isAdd, int[] weight, int[] weighted, int[] bag_value) {
        this.n = n;
        this.m = m;
        this.bag_value = bag_value;
        this.isAdd = isAdd;
        this.item_values = item_values;
        this.weight = weight;
        this.weighted = weighted;
        this.item_weight = item_weight;
        benefits = new float[n];
        for (int i = 0; i < n; i++) {
            benefits[i] = (float) (this.item_values[i] / this.item_weight[i] * 1.0);
        }
    }

    private void initiate() {//随机数生成物品的重量和价值
        for (int i = 0; i < n; i++) {
            item_weight[i] = 5 + (int) (Math.random() * 15 + 1);
            item_values[i] = 5 + (int) (Math.random() * 15 + 1);
            benefits[i] = (float) (item_values[i] / item_weight[i] * 1.0);
            for (int j = 0; j < m + 1; j++) {
                isAdd[i][j] = 0;
            }
        }
        for (int i = 0; i < m; i++) {
            weight[i] = 10 + (int) (Math.random() * 15 + 1);
            weighted[i] = 0;
            bag_value[i] = 0;
        }
        for (int i = 0; i < n; i++) {
            System.out.println("物品" + (i + 1) + " weight:" + item_weight[i] + " value:" + item_values[i]);
        }
        for (int i = 0; i < m; i++) {
            int w = weight[i] + weighted[i];
            System.out.println("背包" + (i + 1) + " weight:" + w);
        }
    }

    private int sum(int[] arr) {
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }
        return sum;
    }

    private void sort() {
        for (int i = 0; i < m - 1; i++) {
            for (int j = i + 1; j < m; j++) {
                if (weight[i] > weight[j]) {
                    changeLocation(i, j);
                }
            }
        }
    }

    private void changeLocation(int i, int j) {
        int w = weight[i];
        weight[i] = weight[j];
        weight[j] = w;

        int wed = weighted[i];
        weighted[i] = weighted[j];
        weighted[j] = wed;

        int v = bag_value[i];
        bag_value[i] = bag_value[j];
        bag_value[j] = v;

        for (int k = 0; k < n; k++) {
            int demo = isAdd[k][i];
            isAdd[k][i] = isAdd[k][j];
            isAdd[k][j] = demo;
        }
    }

    private int getIndex() {
        int index = -1;//存放未被放入背包且可以被放入的item的index
        for (int i = 0; i < n; i++) {
            if (sum(isAdd[i]) == 0) {//item是否被放入某个背包中，最后一位存放是否能被放入现有背包空余，1为否,0则可以放入12
                index = i;
                break;
            }
        }
        return index;
    }

    public void afterSort(int index) { //item放入背包后，对当前所有背包进行剩余空间大小排序
        if (index > 0) {
            for (int i = index - 1; i >= 0; i--) {
                if (weight[index] < weight[i]) {
                    changeLocation(index, i);
                    index = i;
                }
            }
        }
    }

    public void removeSort(int index) { //item取出背包后排序，更新当前顺序
        if (index < m - 1) {
            for (int i = index + 1; i < m; i++) {
                if (weight[index] > weight[i]) {
                    changeLocation(index, i);
                    index = i;
                }
            }
        }
    }

    public void add() {
        if (m > 1) {
            int be_index = getIndex(); //找到并存放未被放入背包且benefit最大的物品的index
            while (be_index != -1) {
                for (int i = be_index; i < n; i++) {
                    if (benefits[be_index] < benefits[i] && sum(isAdd[i]) == 0) {
                        be_index = i;
                    }
                }
                int kn_index = -1; //找到当前能放入该物品的剩余空间最小的背包
                for (int i = 0; i < m; i++) {
                    if (weight[i] > item_weight[be_index]) {
                        kn_index = i;
                        break;
                    }
                }
                if (kn_index != -1) {
                    addWeight(be_index, kn_index);
                    afterSort(kn_index);
                } else {
                    isAdd[be_index][m] = 1;//该物品无法放入此包
                }
                be_index = getIndex();
            }
            Output();
        }
    }

    public int getTotalValue() {
        int v = 0;
        for (int i = 0; i < m; i++) {
            v += bag_value[i];
        }
        return v;
    }

    public void Output() {

        for (int i = 0; i < m; i++) {
            int w = weight[i] + weighted[i];
            System.out.println("背包" + (i + 1) + " (weight:" + w + " value:" + bag_value[i] + ")");
            for (int j = 0; j < n; j++) {
                if (isAdd[j][i] == 1) {
                    System.out.println("物品" + (j + 1) + " -> 背包" + (i + 1) + " weight:" + item_weight[j] + " value:" + item_values[j]);
                }
            }
            System.out.println();
        }
        System.out.println("total value: " + getTotalValue());
        System.out.println();
    }

    public static void main(String[] args) {
        GreedyAlgorithm greedy = new GreedyAlgorithm();
        System.out.println("Greedy Search");
        greedy.add();
    }

    public int[] getWeightArr() {
        return weight;
    }

    public void addWeight(int item_index, int kn_index) {
        weight[kn_index] -= item_weight[item_index];
        weighted[kn_index] += item_weight[item_index];
        bag_value[kn_index] += item_values[item_index];
        isAdd[item_index][kn_index] = 1;
    }

    public void removeWeight(int item_index, int kn_index) {
        weight[kn_index] += item_weight[item_index];
        weighted[kn_index] -= item_weight[item_index];
        bag_value[kn_index] -= item_values[item_index];
        isAdd[item_index][kn_index] = 0;
    }

    public void removeAdded() { //将item从无法被放入包的队列中取出
        for (int i = 0; i < n; i++) {
            isAdd[i][m] = 0;
        }
    }

    public int[] isRemove(int kn, int weight) {
        int v = 0;
        int[] items = new int[n];
        int num = 0;
        for (int i = 0; i < n; i++) {
            if (isAdd[i][kn] == 1) {
                items[num++] = i;
            }
        }
        for (int i = 0; i < num - 1; i++) {
            for (int j = i + 1; j < num; j++) {
                if (item_values[items[i]] > item_values[items[j]]) {
                    int demo = items[i];
                    items[i] = items[j];
                    items[j] = demo;
                }
            }
        }
        int wed = 0;
        int[] remove = new int[num + 1];
        int exist = 0;
        for (int i = 0; i < num; i++) {
            wed += item_weight[items[i]];
            v += item_values[items[i]];
            remove[++exist] = items[i];
            if (item_weight[items[i]] > weight) {
                v = item_values[items[i]];
                for (int j = 1; j < num + 1; j++) {
                    remove[j] = -1;
                }
                remove[1] = items[i];
                break;
            } else if (wed > weight) {
                break;
            }
        }
        remove[0] = v;
        return remove;
    }

    public void Filling(int kn) {
        int[] index = new int[2];
        for (int i = 0; i < 2; i++) {
            index[i] = -1;
        }
        int v = 0;
        for (int i = 0; i < n; i++) {
            if (item_weight[i] <= weight[kn] && sum(isAdd[i]) == 0 && item_values[i] > v) {
                index[0] = i;
                index[1] = 0;//为0未被放入包内
                v = item_values[i];
            } else if (item_weight[i] <= weight[kn] && item_values[i] > v && getAddedIndex(i) > kn) {
                index[0] = i;
                index[1] = 1;//为1在其他包内
                v = item_values[i];
            } else if (item_weight[i] <= weight[kn] + weighted[kn] && item_values[i] > isRemove(kn, item_weight[i])[0] && sum(isAdd[i]) == 0) {
                index[0] = i;
                index[1] = -1;//为-1需要将包中其他item拿出来
            }
        }
        if (index[0] != -1) {
            if (index[1] == 1) {
                removeWeight(index[0], getAddedIndex(index[0]));
                removeSort(index[0]);
            } else if (index[1] == -1) {
                int[] demo = isRemove(kn, item_weight[index[0]]);
                for (int i = 1; i < demo.length; i++) {
                    if (demo[i] != -1) {
                        removeWeight(demo[i], kn);
                    } else {
                        break;
                    }
                }
                removeSort(index[0]);
            }
            addWeight(index[0], kn);
            afterSort(kn);
        }
    }

    private int getAddedIndex(int item) {
        int index = -1;
        for (int i = 0; i < m; i++) {
            if (isAdd[item][i] == 1) {
                index = i;
                break;
            }
        }
        return index;
    }

    public void setN(int n) {
        this.n = n;
    }

    public int getN() {
        return this.n;
    }

    public void setM(int m) {
        this.m = m;
    }

    public int getM() {
        return this.m;
    }

    public void setBag_value(int[] bag_value) {
        this.bag_value = bag_value;
    }

    public int[] getBag_value() {
        return this.bag_value;
    }

    public int[][] getisAdd() {
        return isAdd;
    }

    public void setisAdd(int[][] isAdd) {
        this.isAdd = isAdd;
    }

    public void setItem_values(int[] item_values) {
        this.item_values = item_values;
    }

    public int[] getItem_values() {
        return this.item_values;
    }

    public void setWeight(int[] weight) {
        this.weight = weight;
    }

    public int[] getWeight() {
        return this.weight;
    }

    public void setItem_weight(int[] item_weight) {
        this.item_weight = item_weight;
    }

    public int[] getItem_weight() {
        return this.item_weight;
    }

    public void setWeighted(int[] weighted) {
        this.weighted = weighted;
    }

    public int[] getWeighted() {
        return this.weighted;
    }
}


